class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> memo(m + 1, vector<int>(n + 1));
        return dfs(m, n, memo);
    }
 
    int dfs(int sr, int sc, vector<vector<int>>& memo)
    {
        if(sr == 0 || sc == 0)
            return 0;
        if(sr == 1 && sc == 1)
            return 1;
 
        if(memo[sr][sc] != 0)
            return memo[sr][sc];
        
        memo[sr][sc] = dfs(sr - 1, sc, memo) + dfs(sr, sc - 1, memo);
        return memo[sr][sc];
    }
};